package reviewAlgorithms.ListNode;

public class IsPalindrome {
    public static void main(String[] args) {

    }
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }
        int length = 0;
        ListNode currentNode = head;
        ListNode head2;
        while (currentNode != null){
            length ++;
            currentNode = currentNode.next;
        }
        currentNode = head;
        int cutIndex = length / 2;
        for (int i = 0; i < cutIndex - 1; i++) {
            currentNode = currentNode.next;
        }
        if (length % 2 == 0){
            head2 = reverse(currentNode.next);
        }else {
            head2 = reverse(currentNode.next.next);
        }
        while (head != null && head2 != null){
            if (head.val != head2.val){
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
    public static ListNode reverse(ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode newHead = head;
        ListNode currentNode = head.next;
        head.next = null;
        while (currentNode!= null){
            ListNode next = currentNode.next;
            currentNode.next = newHead;
            newHead = currentNode;
            currentNode = next;
        }
        return newHead;
    }
}
